package BinaryTreeExer;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-07-21
 * Time: 10:04
 */

/**
 * 二叉搜索树与双向链表:
 *
 * 描述
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示
 *
 *

 * 注意:
 * 1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
 * 2.返回链表中的第一个节点的指针
 * 3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构
 * 4.你不用输出双向链表，程序会根据你的返回值自动打印输出
 * 输入描述：
 * 二叉树的根节点
 * 返回值描述：
 * 双向链表的其中一个头节点。
 * 示例1
 * 输入：
 * {10,6,14,4,8,12,16}
 * 复制
 * 返回值：
 * From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;
 * 复制
 * 说明：
 * 输入题面图中二叉树，输出的时候将双向链表的头节点返回即可。
 * 示例2
 * 输入：
 * {5,4,#,3,#,2,#,1}
 * 复制
 * 返回值：
 * From left to right are:1,2,3,4,5;From right to left are:5,4,3,2,1
 */
public class BinaryExercise2 {

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }

    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }

        ConvertChild(pRootOfTree);

        //找头节点
        TreeNode head = pRootOfTree;
        while (head.left != null) {
            head = head.left;
        }

        return head;
    }

    //prev是用来记录'每次'要修改节点的前一个节点
    TreeNode prev = null;

    public void ConvertChild(TreeNode root) {
        //中序遍历
        if (root == null) {
            return;
        }

        //左
        ConvertChild(root.left);

        //根
        root.left = prev;
        //在树第一次来到最左边，prev是空
        if (prev != null) {
            prev.right = root;

        }

        //每个节点的左右节点改了，才可以‘每次’的走
        prev = root;

        //右
        ConvertChild(root.right);

    }
}
